/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package huffmanlab;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;

/**
 * Weight balanced tree
 * @author Xearus
 */
public class HuffmanTree implements Iterable<HuffmanCharacter> {
    private class Node {
        public final long Weight;
        
        public final boolean HaveValue;
        public final int Value;
        public final Node Left;
        public final Node Right;
        
        public Node(Node left, Node right) {
            Weight = left.Weight + right.Weight;
            Left = left;
            Right = right;
            Value = 0;
            HaveValue = false;
        }
        
        public Node(int value, long weight) {
            Weight = weight;
            Left = null;
            Right = null;
            Value = value;
            HaveValue = true;
        }
    }
    
    private Node _Root;
    public long getWeight() {
        return _Root.Weight;
    }
    
    public HuffmanTree() {
        _Root = null;
    }
    
    private void Add(Node node)
    {
        if(_Root != null)
        {
            // Add new value to the left side of the new node
            _Root = new Node(node, _Root);
        }
        else
        {
            _Root = node;
        }
    }
    
    public void Add(HuffmanCharacter value)
    {
        Add(new Node(value.Value, value.Weight));
    }
    
    public void Add(Character value, long weight) {
        int realValue = value.charValue();
        if(realValue < 0) {
            realValue += Byte.MAX_VALUE;
        }
        Add(new Node(realValue, weight));
    }
    
    public void Add(HuffmanTree tree)
    {
        Add(tree._Root);
    }
    
    private class NodeIterator implements Iterator<HuffmanCharacter> {
        private ArrayList<HuffmanCharacter> _Characters;
        private int _Index;
        
        public NodeIterator(Node root) {
            _Index = -1;
            _Characters = new ArrayList<HuffmanCharacter>();
            BuildHuffmanCharacterList(root, _Characters, new Stack<Side>());
        }
        
        private void BuildHuffmanCharacterList(Node node, ArrayList<HuffmanCharacter> characters, Stack<Side> visited)
        {
            if(node.HaveValue) {
                characters.add(new HuffmanCharacter(node.Value, node.Weight, ConvertToArray(visited)));
            } else {
                Stack<Side> s;
                
                s= new Stack<>();
                s.addAll(visited);
                s.push(Side.Left);
                BuildHuffmanCharacterList(node.Left, characters, s);
                
                s = new Stack<>();
                s.addAll(visited);
                s.push(Side.Right);
                BuildHuffmanCharacterList(node.Right, characters, s);
            }
        }
        
        private Side[] ConvertToArray(Stack<Side> path)
        {
            Side[] p = new Side[path.size()];
            for(int i = 0; i < path.size();i++){
                p[i] = path.get(i);
            }
            return p;
        }
        
        @Override
        public boolean hasNext() {
            return (_Index + 1) < _Characters.size();
        }

        @Override
        public HuffmanCharacter next() {
            HuffmanCharacter ret = null;
            if(hasNext())
            {
                _Index++;
                ret = _Characters.get(_Index);
            }
            return ret;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Will never be supported. This method doesn't belong to and iterator which is supposed to iterate and ONLY iterate... Java smells");
        }
    }
    
    @Override
    public Iterator<HuffmanCharacter> iterator() {
        return new NodeIterator(_Root);
    }
}
